/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.twopoint;

/**
 * <p>
 * 容器盛水
 * 数组每个元素代表从x轴到该元素值并且宽度为1的柱子，求最多能乘多少水。
 * 
 * Given [0,1,0,2,1,0,1,3,2,1,2,1], 
 * return 6. 
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class TrappingRainWater {
    //每根柱子所盛水量由左右两边的柱子决定
    public int trap(int[] height) {
      int n = height.length;
      int result = 0;
      int high = 0;//第一个指针指向最高的柱子
      for(int i=0;i<n;i++){
          if(height[i]>height[high]){
              high = i;
          }
      }
      int second = 0;//第二个指针记录之前扫描的最高柱子
      //从首段开始扫描，求左半部分的水
      for(int i=0;i<high;i++){
          if(second>height[i]){
              //求出这三根柱子挨着所盛水 secon,i,high
              result += second-height[i];
          }else{
              second = height[i];
          }
      }
      second = 0;
      for(int i=n-1;i>high;i--){
          if(second>height[i]){
              result +=second-height[i];
          }else{
              second = height[i];
          }
      }
      return result;
      
    }
}
